The invention relates to the vector quantization and inverse vector quantization of a digitized image.
Vector quantization, and the inverse vector quantization connected therewith, is used for coding and compression of digitized images. It is based on the division of the image into two-dimensional image regions, and the determination of a code word that describes the respective image region to be quantized at best approximately, with respect to a predeterminable similarity criterion. Code words are vectors that have previously been stored as a set of standard vectors in what is called a code book. From the code book, vectors are imaged approximately onto vectors that describe the image information of the image region to be quantized. From this procedure, there also results the concept of vector quantization.
In the context of this document, an image region is to be understood as a set of image points of the digital image respectively to be quantized. The image regions can comprise an arbitrary shape and size.
In the following, a quantization vector is designated as a vector that is contained in a code book and that contains as vector components values of image information that are to be quantized. vector. In the following, the index is designated an entry of the code book. With the entry, the respective quantization vector is unambiguously identified. However, it is likewise possible to use the quantization vector itself as an entry of the code book.
Standardly, the entry of the code book is coded and is transmitted to a receiver.
For the reconstruction of the digitized image, after the decoding in a code book also present at the receiver, the received entry is imaged onto the quantization vector, and the quantization vector is used as an item of approximated image information for the reconstruction of the digitized image.
By means of this procedure, the required transmission rate for the transmission of the image information of the digitized image is reduced considerably, since only the index of the code book need respectively be transmitted, and not the entire image vector of the respective image block.
From the prior art document R. F. Chang and W. T. Chen, Image Coding using Variable-Side-Match Finite-State Vector Quantization, IEEE Transactions Image Processing, vol. 2, pp. 104-108, January 1993, it is known in addition to exploit correlations between image blocks, in order in this way to reduce further the required transmission rate. The method specified in the first cited prior art document T. Kim, New Finite State Vector Quantizers for Images, Proceedings of ICASSP, pp. 1180-1183, 1988 is designated as a finite state vector quantization (FSVQ). The respective state of the current input vector is defined by the respective image vector or, respectively, quantization vector immediately previously coded, i.e. quantized. The finite state vector quantization is a class of vector quantizations that use digital memories as described in R. F. Chang and W. T. Chen, Image Coding using Variable-Side-Match Finite-State Vector Quantization, IEEE Transactions Image Processing, vol. 2, pp. 104-108, January 1993.
In the following, an image vector is designated as a vector that respectively describes an image region, and which contains as vector components the image information to be quantized of the respective image region.
Under image information, for example luminance information, a brightness value allocated to the respective image point, chrominance information, a color value allocated to the respective image point, or also for example spectral coefficients, e.g. DCT transformation coefficients (Discrete Cosine Transformation), are described.
It is known to group a digitized image to be coded into two-dimensional image regions with a rectangular shape T. Kim, New Finite State Vector Quantizers for Images, Proceedings of ICASSP, pp. 1180-1183, 1988. The image points of the image are thereby grouped into what are called image blocks.
Standardly, luminance values and/or chrominance values are allocated to the image points of the image block. The luminance values and/or the chrominance values of the respective image points respectively form, as a component of the image vector, the image vector to be quantized. In the known method, the image vector to be quantized is compared with the set of quantization vectors of the code book, which standardly have been stored previously and were for example stored in a read-only memory (ROM). The quantization vector of the code book is selected that is most similar to the image vector with respect to a predeterminable similarity measure. As a similarity measure, the sum of the quadratic difference of the individual components of the image vector and of the quantization vector is standardly used. If the xe2x80x9cbestxe2x80x9d quantization vector has been determined, an index of the code book is standardly calculated for the identification of the quantization In the first cited prior art document T. Kim, New Finite State Vector Quantizers for Images, Proceedings of ICASSP, pp. 1180-1183, 1988, in addition two methods of finite state vector quantization (FSVQ) are described: what is called side-match vector quantization (SMVQ) and what is called overlap-match vector quantization (OMVQ).
Both methods have the aim of solving the problem of block artefacts that arise during the coding of image blocks.
In the SMVQ, it is presupposed that the distribution of the luminance information of the lines and columns of the image to be quantized can be described with a first-order Markov process, i.e. that the luminance values, allocated to the image points, of adjacent lines and columns are correlated with one another to a high degree. Under this presupposition, image points at the edge of the image blocks of an image block to be coded respectively contain a large part of the image information of previously coded adjacent image blocks. What is known as a state code book is formed, which contains code words that contain edge image points that comprise a high degree of similarity in comparison with edge image points already coded previously. The state code book is used for the selection of the most similar quantization vector of the code book for the respective image block. An advantage of the SMVQ or, respectively, of the FSVQ is that even for the case in which the image vector is not optimally described by the quantization vector, the error that arises is often not excessively visible to an observer of the reconstructed image, due to the correlation of adjacent image blocks.
In the OMVQ method, image blocks to be quantized are formed in that lines or, respectively, columns of adjacent image blocks partially overlap. For the determination of the quantization vector for the respective image block, the same procedure is used as in the FSVQ method or, respectively, in the SMVQ method. In the reconstruction of the image, the respective image block is again brought to its original size by respectively supplementing the overlapping lines or, respectively, columns between the image blocks with a line or, respectively, column of image points of which the average of the brightness values or, respectively, color values is assigned to the overlapping image points.
The known methods comprise some considerable disadvantages. For one, the methods are very complex, which leads to a considerable computing time requirement in the execution of the method by a computer.
In the context of this document, both an electrical data processing and also an arbitrary arrangement with a processor with which digital data can be processed are to be understood as computers.
In addition, the known methods presuppose a first-order Markov process, i.e. a high degree of correlation of adjacent image points of the digitized image. In the method, an additional indication of the state, i.e. an additional indication and taking into account of information of previously coded image blocks, is also required, which leads in turn to an increase in the required transmission rate.
Basic principles of vector quantization are described in the prior art document, N. Nasrabadi and R. King, Image Coding using Vector Quantization: A Review, IEEE Transactions on Communications, vol. 36, no. Aug. 8, 1988.
The invention is thus based on the problem of indicating a method for vector quantization and for inverse vector quantization of a digitized image in which the disadvantages of the known methods are avoided.
In general terms the present invention is a computer implemented method for vector quantization and for inverse vector quantization of a digitized image. At least a part of image points of the digitized image is grouped into at least one image region to be quantized and into at least one image region that is not to be quantized. Image information of the image region to be quantized is imaged onto an entry in a code book with which the respective image information of the image region to be quantized is approximately described. The respective entry of the code book is allocated to the image region to be quantized. The entry is imaged onto an approximated item of image information contained in the code book. The quantized image region is reconstructed from the approximated image information. The region of the image that was not quantized is reconstructed by means of interpolation and/or extrapolation of image information of the quantized image region.
Advantageous developments of the present invention are as follows.
The image region to be quantized is constructed with a rectangular shape.
The image region to be quantized is reconstructed using approximated image information of directly adjacent image regions.
Luminance values and/or chrominance values are used that are allocated to the image points of the image.
The size of the image region is adaptively constructed.
The size of the image region is selected dependent on the semantics of the image to be quantized.
The semantics of the image to be quantized is represented by a measure with which the change of image information within the image is represented.
The digitized image is divided into at least one image region to be quantized and into at least one image region that is not to be quantized. The image regions to be quantized are imaged in a code book by imaging the image information of the image regions onto at least one entry. This imaging is also designated vector quantization. The respective entry of the code book is allocated to the image region, and in the reconstruction of the digitized image the entry is imaged onto the approximated image information allocated to the entry in the code book. Using the approximated image information, the respective image region is reconstructed. Image points, i.e. image regions of the digitized image, that were not quantized are reconstructed by interpolation and/or extrapolation of image information of at least one quantized image region.
In this very simple way, it is possible to avoid having to quantize the entire digitized image; rather, only a sub-region of the digitized image need be quantized.
In relation to the known methods, it is not necessary that it be possible to describe the curve of the image information by means of a first-order Markov process.
In relation to the known methods, the method is considerably simplified in its execution. This has the result that a considerable reduction of the required computing capacity for quantization and for inverse quantization, and thus for the overall coding or, respectively, decoding of the digitized image, is achieved.
A further reduction of a bandwidth requirement required in the transmission of the image is achieved in that the size of the image regions to be quantized is constructed adaptively, i.e., that for example, dependent on the semantics of the digitized image, image regions of different size are selected as image regions to be quantized. In this way, for example given very uniform image regions with high redundancy within the image information, a small size of the image region to be quantized will already suffice to ensure a good quality of the constructed image. On the other hand, for example in regions of the image that comprise very detailed structures, a quantization of larger image regions is necessary to enable these regions actually to be simulated well. If image regions of small size are quantized, interpolation takes place over a larger number of image points of non-quantized image regions, and, conversely, given larger image regions to be quantized, interpolation or, respectively, extrapolation takes place only over a small number of non-quantized image points.
In this way, an optimized matching of the required transmission rate to the semantics of the image is possible.
In addition, it is advantageous to take into account prior knowledge concerning the image, for example prior knowledge concerning very uniform image regions with respect to the image information and concerning image regions with very detailed construction in the selection of the size of the image region that is respectively to be quantized. This development also achieves an improvement of the required transmission rate.